//
//  main.c
//  堆排序sort
//
//  Created by Song on 2018/4/9.
//  Copyright © 2018年 Song. All rights reserved.
//


//  堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
//  一般升序采用大顶堆，降序采用小顶堆

//  大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
//  小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

//  对于编号是从1开始的树: 子节点编号为i，其父节点编号为 i/2  (编号从0开始的树，父节点为 (i-1)/2)

#include <stdio.h>

#define length 9

// 交换元素
void swap(int arr[], int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

// 调整大顶堆 （仅仅是调整，建立在大顶堆已构建的基础上）
void adjustHeap(int arr[], int i, int length2) {
    // i：父节点编号  k：i*2左子节点编号   k+1: i*2+1 右子节点编号
    // arr[i-1]:父节点  arr[k-1]:左子节点  arr[k]:右子节点
    int temp = arr[i-1];
    int k = i*2;
    printf("父节点 temp = %d\n",temp);
    printf("左子节点 arr[k-1] = %d\n",arr[k-1]);
    printf("右子节点 arr[k] = %d\n",arr[k]);
    printf("父节点编号 i = %d\n",i);
    printf("左子节点编号 k = %d\n",k);
    printf("右子节点编号  = %d\n",k+1);
    
    for ( k = i*2; k<=length2; k = k*2) { //从i结点的左子结点开始，也就是编号为k=i*2处开始
        if (k < length2 && arr[k-1] < arr[k]) { //如果左子结点小于右子结点，k指向右子结点
            k++; // k指向较大者
        }
        if (arr[k-1] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            arr[i-1] = arr[k-1];
            i = k;
        } else {
            break;
        }
    }
    arr[i-1] = temp;
    printf("=========================\n");
}

// 排序: 堆的编号为 1 -- length (编号与数组下标相差1)
void sort(int arr[]) {
    // 1.构建大顶堆
    for (int i = length/2; i>=1; i--) { // 从最后一个非叶子节点，从下至上，从右至左调整
        adjustHeap(arr, i, length);
    }
    printf("\n\n\n\n");
    // 2.调整堆结构 + 交换堆顶元素与末尾元素
    for (int j = 1; j<length; j++) {
        swap(arr, 0, length-j);
        for (int a = 0; a<length; a++) {
            printf("%d ",arr[a]);
        }
        adjustHeap(arr, 1, length-j); // 编号为1
    }
}


int main(int argc, const char * argv[]) {
    
//    int arr[] = {9,8,7,6,5,4,3,2,1};
    int arr[] = {5,4,6,3,7,2,8,9,1};
    for (int a = 0; a<length; a++) {
        printf("%d ",arr[a]);
    }
    printf("\n");
    
    sort(arr);
    
    printf("排序后：");
    for (int a = 0; a<length; a++) {
        printf("%d ",arr[a]);
    }
    
    printf("\n");
    return 0;
}



// 以下为 堆的编号为 0 -- length-1 (编号与数组下标相等)

//#include <stdio.h>
//
//#define length 9
//
//// 交换元素
//void swap(int arr[], int a, int b) {
//    int temp = arr[a];
//    arr[a] = arr[b];
//    arr[b] = temp;
//}
//
//// 调整大顶堆 （仅仅是调整，建立在大顶堆已构建的基础上）
//void adjustHeap(int arr[], int i, int length2) {
//    int temp = arr[i];
//    printf("temp = %d\n",temp);
//    printf("i = %d\n",i);
//    printf("k = %d\n",i*2+1);
//    printf("=========================\n");
//    for (int k = i*2+1; k<length2; k = k*2+1) { //从i结点的左子结点开始，也就是2i+1处开始
//        // k+1 为arr[i]的子节点 length-1
//        if (k+1 < length2 && arr[k] < arr[k+1]) { //如果左子结点小于右子结点，k指向右子结点
//            k++;
//        }
//        if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
//            arr[i] = arr[k];
//            i = k;
//        } else {
//            break;
//        }
//    }
//    arr[i] = temp;
//}
//
//// 排序: 堆的编号为 0 -- length-1
//void sort(int arr[]) {
//    // 1.构建大顶堆
//    for (int i = length/2-1; i>=0; i--) { // ((length-1)-1)/2 = length/2-1
//        // 从最后一个非叶子节点(i=[(length-1)-1]/2)，从下至上，从左至右调整
//        adjustHeap(arr, i, length);
//    }
//    // 2.调整堆结构 + 交换堆顶元素与末尾元素
//    for (int j = length-1; j>0; j--) {
//        swap(arr, 0, j);
//        adjustHeap(arr, 0, j);
//    }
//}
//
//
//int main(int argc, const char * argv[]) {
//    
//    //    int arr[] = {9,8,7,6,5,4,3,2,1};
//    int arr[] = {5,4,6,3,7,2,8,9,1};
//    for (int a = 0; a<length; a++) {
//        printf("%d ",arr[a]);
//    }
//    printf("\n");
//    
//    sort(arr);
//    
//    printf("排序后：");
//    for (int a = 0; a<length; a++) {
//        printf("%d ",arr[a]);
//    }
//    
//    printf("\n");
//    return 0;
//}

